Méthodes de Monte Carlo¶
6. Prédiction avec échantillonnage préférentiel (Importance Sampling)¶
6.3. Méthode de calcul de la prédiction¶
Nous pouvons maintenant mettre en oeuvre un algorithme de Monte-Carlo qui permet de moyenner les revenus obtenus à partir d'un lot d'observations d'épisodes qui suivent la stratégie d'exploration $b$ afin de d'estimer la fonction des valeurs des états $V_\pi(s)$ s'ils étaient visités avec la stratégie $\pi$. Pour cela nous allons introduire quelques notations, et en particulier il est intéressant dans cette situation de numéroter les instants de manière à les incrémenter au fir et à mesure des épisodes observés.
Prenons l'exemple ci-dessous décrivant l'observation d'un lot de 5 épisodes qui suivent la stratégie comportementale $b$ :
Les notations que nous allons utiliser sont les suivantes:
$\tau \left( s \right)$ : Ensemble de tous les instants où l'état $s$ est visité
- Exemple EVMC : [50,53,130,140,145,153,200,310,320,326,330]
- Exemple FVMC : [50,130,200,310,330]
$T(t)$: Ensemble des premiers instants de fin d'épisode qui suivent l'instant t
- Exemples : T[0:99]=100; T[101:148]=149; T[150:298]=299; T[300:323]=324; T[325:398]=399
$G_t$: Revenus après l'instant t jusqu'à l'instant de fin d'épisode T(t)
- Exemples : $G_1$=Revenu[t=1...100]; $G_{160}$=Revenu[t=160...299]; $G_{300}$=Revenu[t=300...324]
${\left\{ {{G_t}} \right\}_{t \in \tau \left( s \right)}}$: Séquence qui contient l'ensemble des revenus des états visités
${\left\{ {{\rho _{t:T(t) - 1}}} \right\}_{t \in \tau \left( s \right)}}$ : Séquence qui contient l'ensemble des ratio d'échantillonage préférentiel des états visités.
Pour estimer $V_\pi(s)$, on calcule la moyenne de tous les revenus obtenus en les pondérant par le ratio d'échantillonnage préférentiel ordinaire:
Lorsque l'échantillonnage préférentiel est obtenu de cette manière (c'est-à-dire en faisant une simple moyenne), on dit qu'il s'agit d'un échantillonnage préférentiel ordinaire.
Une alternative est l'échantillonnage préférentiel pondéré qui utilise une moyenne pondérée:
ou zéro si le dénominateur est nul.
Pour mieux comprendre la différence entre ces deux méthodes, considérons une estimation FVMC après avoir observé un seul revenu depuis l'état $s$:
Avec l'échantillonnage préférentiel pondéré, on obtient ${V_\pi }\left( s \right) = \frac{{\sum\limits_{t \in \tau \left( s \right)} {{\rho _{t:T(t) - 1}}{G_t}} }}{{\sum\limits_{t \in \tau \left( s \right)} {{\rho _{t:T(t) - 1}}} }} = \frac{{{\rho _{t:T(t) - 1}}{G_t}}}{{{\rho _{t:T(t) - 1}}}} = {G_t}$
- L'estimation est donc égale au revenu observé, et cela indépendamment du ratio. Cela a du sens car c'est le seul revenu qui a été observé, mais par contre statistiquement le résultat est biaisé car il s'agit de la $V_b(s)$ et non de $V_\pi(s)$.
- Avec l'échantillonnage préférentiel ordinaire, on obtient ${V_\pi }\left( s \right) = \frac{{\sum\limits_{t \in \tau \left( s \right)} {{\rho _{t:T(t) - 1}}{G_t}} }}{{\left| {\tau \left( s \right)} \right|}} = \frac{{{\rho _{t:T(t) - 1}}{G_t}}}{1} = {\rho _{t:T(t) - 1}}{G_t}$
- Ici l'estimation n'est pas biaisée et il s'agit bien de $V_\pi(s)$.
Cependant, l'échantillonnage préférentiel ordinaire peut être extrême. Si par exemple on suppose que le ratio est de 10 (ce qui signifie que la trajectoire observée est 10 fois plus probable sous la stratégie cible que sous la stratégie comportementale) alors dans ce cas, l'estimation serait 10 fois plus importante que le revenu observé. Cette valeur pourrait être très éloignée de la valeur observée même si la trajectoire de l'épisode observé est considérée comme très représentative de la stratégie cible.
De manière plus formelle, la différence entre ces deux méthodes dans le cadre de la FVMC est quantifiée par la valeur de leurs biais et de leurs variances. L'échantillonnage préférentiel ordinaire et non biaisé alors que l'échantillonnage préférentiel pondéré et biaisé (même si ce biais tend vers zéro pour un grand nombre d'échantillons). Par contre la variance de l'échantillonnage ordinaire est en général non délimité alors que dans l'échantillonnage pondéré cette variance est finie. En pratique l'échantillonnage pondéré a généralement une variance beaucoup plus faible est fortement conseillé.
Enfin pour terminer précisons que l'échantillonnage ordinaire reste très important car il permette de mettre en place des méthodes d'approximation de fonctions dans les cas où les MDP ne sont pas discrets mais sont continus.
Dans le cadre des EVMC les deux méthodes d'échantillonnage sont biaisées mais le biais tend pour chacune d'elle vers zéro de manière asymptotique lorsque le nombre d'échantillons augmente. En pratique la méthode EVMC est souvent préférée parce qu'elle permet de ne pas garder trace des états visités.